package com.uhu.code;

import java.util.HashMap;
import java.util.Map;

/**
 * 146. LRU 缓存
 * https://leetcode.cn/problems/lru-cache/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class Solution146 {
    static class LRUCache {

        // 定义双向链表
        static class ListNode {
            int key;
            int value;
            ListNode prev;
            ListNode next;

            public ListNode() {
            }

            public ListNode(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }


        // 记录key 节点
        private Map<Integer, ListNode> cache = new HashMap<>();
        private int size;
        private int capacity;
        private ListNode head;
        private ListNode tail;

        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            //创建虚拟头尾节点
            this.head = new ListNode();
            this.tail = new ListNode();
            this.head.next = this.tail;
            this.tail.next = this.head;
        }

        public int get(int key) {
            ListNode tempNode = cache.get(key);
            if (tempNode != null) {
                // 移除该节点
                removeNode(tempNode);
                // 添加到头部
                addHeadNode(tempNode);
                return tempNode.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            ListNode tempNode = cache.get(key);
            if (tempNode != null) {
                // 移除该节点
                removeNode(tempNode);
                // 添加新节点到头部
                ListNode newNode = new ListNode(key, value);
                addHeadNode(newNode);
                // 添加新节点到cache
                cache.put(key, newNode);
            } else {
                size++;
                if (size > capacity) {
                    //淘态尾部节点
                    cache.remove(tail.prev.key);
                    //移除节点
                    removeNode(tail.prev);
                    size--;
                }
                // 新增节点
                ListNode newNode = new ListNode(key, value);
                addHeadNode(newNode);
                cache.put(key, newNode);
            }
        }

        public void addHeadNode(ListNode tempNode) {
            tempNode.prev = this.head;
            tempNode.next = this.head.next;
            this.head.next.prev = tempNode;
            this.head.next = tempNode;
        }

        public void removeNode(ListNode tempNode) {
            tempNode.prev.next = tempNode.next;
            tempNode.next.prev = tempNode.prev;
        }
    }

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
}
